1109. 航班预订统计

Similar Question

Solution Tips

方案一: 前缀和差分

var corpFlightBookings = function(bookings, n) {
    // 考察差分数组的基本操作
    // 长度未知, 初始化为0即可, 一边做区间加法即可
    const diff = [];
    for (const [start, end, increment] of bookings) {
        // 给 start 到 end 之间的区间加上 increment
        // 等价于给差分数组 [start 加上 increment
        // end +1 减去 increment
        diff[start - 1] = (diff[start - 1] ?? 0) + increment;
        diff[end] = (diff[end] ?? 0) - increment;
    }

    // 通过前缀和操作还原差分数组为原数组
    // 但是差分数组有可能会有空位, 难道需要反过来还原?
    const origin = [];
    origin[0] = diff[0] ?? 0;
    for (let i = 1; i < n; i++) {
        // 如果 diff[i] 为空, 说明 diff[i] 就是 0
        // origin[i] = origin[i - 1]
        origin[i] = origin[i - 1] + (diff[i] ?? 0)
    }

    return origin;
};

let bookings = [[2,3,30],[2,3,45],[2,3,15],[1,3,15]], n = 4
console.log(corpFlightBookings(bookings, n))